package com.atguigu.greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

public class ProfitProblem {
    public static int findTheMaxProfit(int[] costs,int[] profits,int k,int m){
        //m为启动资金，k为最多可做k个项目
        //初始化Node数组
        Node[] nodes=new Node[costs.length];
        int len=costs.length;
        for(int i=0;i<len;i++){
            nodes[i].cost=costs[i];
            nodes[i].profit=profits[i];
        }
        PriorityQueue<Node> costQueue=new PriorityQueue<>(new MinCost());
        PriorityQueue<Node> profitQueue=new PriorityQueue<>(new MaxProfit());
        for(int i=0;i<len;i++){
            costQueue.add(nodes[i]);
        }
        while(k>0) {
            while (costQueue.peek().cost <= m && !costQueue.isEmpty()) {
                profitQueue.add(costQueue.poll()); //将小于m的全部弹出并放入利润的堆中
            }
            if(profitQueue.isEmpty()){
                return m;
            }
            m += profitQueue.poll().profit;
            k--;
        }
        return m;
    }

    public static class Node{
        public int profit;
        public int cost;
        public Node(int profit,int cost){
            this.profit=profit;
            this.cost=cost;
        }
    }

    //成本比较器
    public static class MinCost implements Comparator<Node>{
        public int compare(Node o1,Node o2){
            return o1.cost-o2.cost;
        }
    }

    //利润的比较器
    public static class MaxProfit implements Comparator<Node>{
        public int compare(Node o1,Node o2){
            return o2.profit-o1.profit;
        }
    }
}
